package primary.primary0;

import java.util.ArrayList;
import java.util.List;

public class S0148排序链表 {

    /**
     * 60， 15
     * 整个先放到list里面，排序了，再一个个摞起来输出返回
     */
    public ListNode sortList(ListNode head) {
        if(head == null || head.next == null){
            return head;
        }
        List<ListNode> sortedList = new ArrayList<>();
        while(head != null){
            sortedList.add(head);
            head = head.next;
        }
        // 一定注意，前-后就是从小到大，
        sortedList.sort((o1, o2) -> o1.val - o2.val);
        ListNode fakeHead = new ListNode(-1);
        ListNode res = fakeHead;
        for (int i = 0; i < sortedList.size(); i++) {
            fakeHead.next = sortedList.get(i);
            fakeHead = fakeHead.next;
        }
        // 注意， 最后一个节点的next需要重置为null
        fakeHead.next = null;
        return res.next;

    }

    public static void main(String[] args) {
        ListNode head = new ListNode(4);
        head.next = new ListNode(2);
        head.next.next = new ListNode(1);
        head.next.next.next = new ListNode(3);
        new S0148排序链表().sortList(head);
    }

    private static class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }
}
